package cn.yza.算法.Leetcode;

import java.util.Arrays;

/** 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
 你可以认为每种硬币的数量是无限的。
 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/coin-change
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author Honglixi
 * @create 2021-11-12 20:39
 */
public class Leetcode322 {
    public static void main(String[] args) {
        int i = coinChange(new int[]{1, 2, 5}, 11);
        System.out.println(i);
    }
    static int[] memo;
    public static int  coinChange(int[] coins, int amount) {
        memo = new int[amount + 1];
        Arrays.fill(memo,-2);
        return dp(coins,amount);
    }
    //要凑出金额n，至少要n个硬币
    private static int dp(int[] coins,int amount) {
        //base case
        if (amount == 0) return 0;
        if (amount < 0) return -1;


        if (memo[amount] != -2) {
            return memo[amount];
        }
        int res = Integer.MAX_VALUE;
        //选择需要硬币最少的那个结果
        for (int coin:coins) {
            //计算子问题的结果
            int subProblem = dp(coins,amount - coin);
            //子问题无解则跳过
            if (subProblem == -1) continue;
            res = Math.min(res,subProblem + 1);
        }
        //把计算结果放入备忘录
        memo[amount] = (res == Integer.MAX_VALUE) ? -1:res;
        return memo[amount];
    }
}
